/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-25
 * Time: 22:42
 */
public class Solution {
    //贪心+二分
    public int lengthOfLIS(int[] nums) {
        int length=nums.length;
        int ans=1;//记录最大严格递增长度
        int[] dp=new int[length];//记录前面的最大递增长度对应的递增数组
        dp[0]=nums[0];
        for(int i=0;i<length;i++){
            if(nums[i]>dp[ans-1]){
                //大于前面的所有值
                //直接添加进去
                dp[ans++]=nums[i];
            }else if(nums[i]<dp[ans-1]){
                //否则二分查找
                //将当前元素插入到合适的位置
                //最大递增长度不用变
                int index=binarySearch(dp,ans,nums[i]);
                dp[index]=nums[i];
            }
        }
        return ans;
    }

    //二分查找,返回应该插入的位置的下标
    //注意这里要考虑清楚返回哪个下标才能确定返回正确的位置
    public int binarySearch(int[]dp,int len,int num){
        int left=0;
        int right=len-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if(dp[mid]==num){
                return mid;
            }
            if(dp[mid]<num){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return left;
    }
}
